// HString.cpp

#include <string>

enum Status
{
    OK,
    ERROR,
};

typedef struct
{
    char *ch;
    int length;
}HString;

Status StrAssign(HString &T, char *chars)
{
    if(T.ch)
    {
        delete(T.ch);
    }

    int i = 0;
    char *c = chars;

    while(c)
    {
        ++i;
        ++c;
    }

    if(!i)
    {
        T.ch = NULL;
        T.length = 0;
    }
    else
    {
        if(!(T.ch = new char))
        {
            return ERROR;
        }
        for(int j = 0; j < i; ++j)
        {
            T.ch[j] = chars[j];
        }
        T.length = i;
    }
    
    return OK;
}

int StrLength(HString S)
{
    return S.length;
}

int StrCompare(HString S, HString T)
{
    // S > T, return > 0; S = T, return = 0; S < T, return < 0;
    for (int i = 0; i < S.length && i < T.length; i++)
    {
        if(S.ch[i] != T.ch[i])
        {
            return S.ch[i] - T.ch[i];
        }
    }
    
    return S.length - T.length;
}

Status ClearString(HString &S)
{
    if(S.ch && S.length > 0)
    {
        delete S.ch;
        S.ch = NULL;
        S.length = 0;
    }

    return OK;
}

Status Concat(HString &T, HString S1, HString S2)
{
    if(T.ch)
    {
        delete(T.ch);
    }

    T.ch = new char[S1.length + S2.length];

    if(!T.ch)
    {
        return ERROR;
    }

    for(int i = 0; i < S1.length; ++i)
    {
        T.ch[i] = S1.ch[i];
    }

    for(int i = 0; i < S2.length; ++i)
    {
        T.ch[S1.length + i] = S2.ch[i];
    }

    T.length = S1.length + S2.length;

    return OK;
}

Status SubString(HString &Sub, HString S, int pos, int len)
{
    if(Sub.ch)
    {
        delete Sub.ch;
    }

    if(pos < 1 || pos >= len || pos + len - 1 >= S.length - 1)
    {
        return ERROR;
    }

    Sub.ch = new char[len];
    Sub.length = len;

    if(!Sub.ch)
    {
        return ERROR;
    }

    for(int i = pos, j = 0; i < pos + len && j < Sub.length; ++i, ++j)
    {
        Sub.ch[j] = S.ch[i];
    }

    return OK;
}

int Index(string S, string T, int pos)
{
    int i = pos;
    int j = 0;

    while(i < S.length && j < T.length)
    {
        if(S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }

    if(j >= T.length)
    {
        return i - T.length;
    }
    else
    {
        return 0;
    }
}

int Index_KMP(string S, string T, int pos)
{
    int i = pos;
    int j = 0;

    while(i < S.length && j < T.length)
    {
        if(j == 0 || S[i] == j[i])
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];
        }
    }

    if(j >= T.length)
    {
        return i - T.length;
    }
    else
    {
        return 0;
    }
}

void get_next(string T, int next[])
{
    int i = 1;
    next[1] = 0;
    int j = 0;

    while(i <= T.length)
    {
        if(j == 0 || T[i-1] == T[j-1])
        {
            ++i;
            ++j;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

void get_nextval(string T, int nextval[])
{
    int i = 1;
    nextval[1] = 0;
    int j = 0;

    while(i <= T.length)
    {
        if(j == 0 || T[i-1] == T[j-1])
        {
            ++i;
            ++j;
            if(T[i-1] != T[j-1])
            {
                nextval[i] = j;
            }
            else
            {
                nextval[i] = nextval[j];
            }
        }
        else
        {
            j = nextval[j];
        }
    }
}
